package com.zdb.algorithm.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DijkstraAlgorithm {

    public static void main(String[] args) {

        Graph graph = createGraph();
        graph.print();
        System.out.println("----------------------");
        graph.dijkstra(6);

    }

    public static Graph createGraph() {
        char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Graph graph = new Graph(vertexs);

        // 增加边
        graph.addEdge('A', 'C', 7);
        graph.addEdge('A', 'B', 5);
        graph.addEdge('A', 'G', 2);
        graph.addEdge('B', 'G', 3);
        graph.addEdge('B', 'D', 9);
        graph.addEdge('C', 'E', 8);
        graph.addEdge('E', 'G', 4);
        graph.addEdge('E', 'F', 5);
        graph.addEdge('F', 'G', 6);
        graph.addEdge('F', 'D', 4);

        return graph;
    }

}

/**
 * 已访问顶点集合
 */
class VisitedVertex {

    /**
     * 记录对一个下标顶点是否已经访问过，1：访问过，0：没有访问过
     */
    private int[] already_arr;

    /**
     * 每个下标对应的值为当前下标顶点的访问路径，与dis同时更新
     */
    private String[] pre_visited;

    /**
     * 记录出发顶点到其他顶点的距离，
     * 比如G点为出发顶点，到其他顶点的距离，会动态更新，求的最小距离就会存放到dis
     */
    private int[] dis;

    /**
     *
     * @param num 顶点的个数
     * @param index 出发顶点下标
     */
    public VisitedVertex(int num, int index) {

        already_arr = new int[num];
        pre_visited = new String[num];
        dis = new int[num];
        Arrays.fill(dis, Graph.INF);
        dis[index] = 0;
    }

    /**
     * 获取下一个访问顶点
     *
     * 下一个访问顶点获取规则：
     * 获取上一轮访问到的顶点中最短距离最短一个
     * 即没有被访问过，dis的值有更新的
     * @return
     */
    public int getNextUpdateVertex() {
        int min=Integer.MAX_VALUE,index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if(already_arr[i] == 0 && dis[i]<min) {
                min = dis[i];
                index = i;
            }
        }
        return index;
    }

    public void print() {
        System.out.println("------ 最短距离 ------");
        System.out.println(Arrays.toString(dis));
    }

    /**
     * 更新index顶点的距离
     * @param index
     * @param distance
     */
    public void updateDis(int index, int distance) {
        dis[index] = distance;
    }

    public int[] getDis() {
        return dis;
    }

    /**
     * 更新访问路径
     * @param index
     */
    public void updatePre(int index) {
        // todo
    }

    /**
     * 判断该顶点是否被访问过
     * @param index
     * @return true:访问过，false:没有访问过
     */
    public boolean isVisited(int index) {
        return already_arr[index] == 1;
    }

    public void markVisited(int index) {
        already_arr[index] = 1;
    }
}

class Graph {
    /**
     顶点
     */
    char[] vertexs;
    /**
     * 存放边及权重
     */
    int[][] weight;
    /**
     顶点与vertexs中下标的对应关系
     */
    Map<Character, Integer> vertex2index;

    private List<Edge> edgeList;

    public static final int INF = Integer.MAX_VALUE;

    public Graph(char[] vertexs) {
        this.vertexs = vertexs;
        vertex2index = new HashMap<>();
        for (int i = 0; i < vertexs.length; i++) {
            vertex2index.put(vertexs[i], i);
        }
        weight = new int[vertexs.length][vertexs.length];
        for(int[] link : weight) {
            for (int i = 0; i < link.length; i++) {
                link[i] = INF;
            }
        }
        edgeList = new ArrayList<>();
    }

    public void dijkstra(int index) {
        VisitedVertex vv = new VisitedVertex(getVertexSize(), index);
        // 访问顶点
        updateDjs(vv, index);

        // 获取下一个访问顶点
        for (int i = 1; i < getVertexSize(); i++) {
            int idx = vv.getNextUpdateVertex();
            updateDjs(vv, idx);
        }
        vv.print();
    }

    /**
     * 使用迪杰斯特拉算法获取最短距离
     * @param vv
     * @param index
     */
    private void updateDjs(VisitedVertex vv, int index) {
        // 标记index已访问
        vv.markVisited(index);
        int len = 0;
        // 遍历 weight[index] 获取能够访问的顶点
        for(int i=0; i<weight[index].length; i++) {
            if(weight[index][i] != INF) {
                // 计算出发顶点->index->i顶点的距离
                len = vv.getDis()[index] + weight[index][i];
                // 如果通过index的距离比原来的距离短，则更新最短距离
                if(len < vv.getDis()[i]) {
                    vv.updateDis(i, len);
                }
            }
        }
    }

    public int getVertexSize() {
        return vertexs.length;
    }

    /**
     * 增加边
     * @param a
     * @param b
     * @param weight
     */
    public void addEdge(char a, char b, int weight) {
        int aIdx = vertex2index.get(a);
        int bIdx = vertex2index.get(b);
        if(this.weight[aIdx][bIdx] == INF && weight != INF) {
            this.weight[aIdx][bIdx] = weight;
            this.weight[bIdx][aIdx] = weight;
            edgeList.add(new Edge(a, b, weight));
        }
    }

    /**
     * 将边排序，根据weight 从小到大排序
     */
    public void sortEdge() {
        edgeList.sort(new Comparator<Edge>() {
            @Override public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
    }

    /**
     * 获取所有的边
     * @return
     */
    public List<Edge> getEdgeList() {
        return edgeList;
    }

    /**
     * 获取终点
     * @param ends 长度为顶点个数，下标为顶点的下标，值为下标对应的顶点的终点
     * @param i 顶点对应的下标
     * @return
     */
    public int getEnd(int[] ends, int i) {
        // 循环找i位置的终点
        // ends[i] != 0 说明这个点已经有边了，
        // ends[i] != i 说明这个点的终点不是自己
        // 那么就去找ends[i]所指向的点(终点)，直到最后一个
        while(ends[i] != 0 && ends[i] != i) {
            i = ends[i];
        }
        return i;
    }

    public int getEdgeNum() {
        return edgeList.size();
    }

    /**
     * 获取顶点的下标
     * @param v
     * @return
     */
    public int getVertexIndex(char v) {
        return vertex2index.get(v);
    }

    /**
     * 通过下标获取顶点
     * @param index
     * @return
     */
    public char getVertexByIndex(int index) {
        return vertexs[index];
    }

    public void print() {
        for(int[] link : weight) {
            System.out.print("[");
            for (int i = 0; i < link.length; i++) {
                if(link[i]==INF) {
                    System.out.printf(" %5s", "INF");
                } else {
                    System.out.printf(" %5d", link[i]);
                }
                if(i != link.length -1) {
                    System.out.print(",");
                }
            }
            System.out.println("]");
        }
    }

    static class Edge {
        private char start;
        private char end;
        private int weight;

        public Edge(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        public char getStart() {
            return start;
        }

        public char getEnd() {
            return end;
        }

        public int getWeight() {
            return weight;
        }

        @Override public String toString() {
            return "[" + start +
                    "-" + end +
                    "(" + weight +
                    ")]";
        }
    }
}
